package com.wang.leetcode;
//leetcode33 搜索旋转排序数组
public class BS_Search {
        public int search(int[] nums, int target) {
            if(nums.length == 0){
                return -1;
            }
            if(nums.length == 1){
                return nums[0] == target ? 0 : -1;
            }
            int left = 0;
            int right = nums.length - 1;
            while (left <= right){
                int mid = left + (right - left) >> 1;
                if(nums[mid] == target){
                    return mid;
                }
                //注意target与nums[right]，nums[left]比较时的边界条件，取 “=”？
                if(nums[left] <= nums[mid]){
                    if(nums[left] <= target && nums[mid] > target){
                        right = mid - 1;
                    }
                    else {
                        left = mid + 1;
                    }
                }
                else {
                    if(nums[mid] < target && nums[right] >= target){
                        left = mid + 1;
                    }
                    else {
                        right = mid - 1;
                    }
                }

            }
            return -1;
        }


}

